// 相交链表

package Leetcode;

class Solution160_1 {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null)
            return null;

        ListNode curA = headA;
        ListNode curB = headB;
        int lengthA = 0;
        int lengthB = 0;
        // 获取长度
        while (curA != null) {
            lengthA++;
            curA = curA.next;
        }
        while (curB != null) {
            lengthB++;
            curB = curB.next;
        }

        // 移动到同样的长度
        if (lengthA > lengthB) {
            int k = lengthA - lengthB;
            while (k-- != 0)
                headA = headA.next;
        }

        if (lengthA < lengthB) {
            int k = lengthB - lengthA;
            while (k-- != 0)
                headB = headB.next;
        }

        while (headA != null && headB != null) {
            if (headA.equals(headB))
                return headA;
            headA = headA.next;
            headB = headB.next;
        }

        return null;
    }
}

class Solution160_2 {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode curA = headA;
        ListNode curB = headB;
        while (curA != null || curB != null) {
            if (curA == null)
                curA = headB;
            if (curB == null)
                curB = headA;
            if (curA.equals(curB))
                return curA;
            curA = curA.next;
            curB = curB.next;
        }
        return null;
    }
}